package sort_;

import org.jetbrains.annotations.NotNull;

/**
 * 1.什么是插入排序
 *  首先将待排序的数组的第一个元素看作是已排序的，其后的a[1,n-1]个元素是未排序的
 *  从头到尾扫描未排序的序列，将扫描到的每一个元素插入到已排序的序列中的适当位置。
 * 2.时间复杂度O(n2)
 * 3.空间复杂度O(1)
 * 4.优化方案
 *  在将一个待排序的序列插入到一个有序的序列中，其实可以使用二分查找快速定位要插入的位置
 *  这样时间复杂度O(nlogn)
 *
 */
public class InsertSort {
    public static void main(String[] args) {
        int[] a={3,44,38,5,47,15,36,26,27,2,46,4,19,50,48};

        insertSort(a);

        print(a);
    }

    private static void insertSort(@NotNull int[] a) {
        int n=a.length;
        for(int i=1;i<n;++i){
            int k=a[i];
            for(int j=i-1;j>=0;--j){
                if(a[j]>k){
                    a[j+1]=a[j];
                }else{
                    a[j+1]=k;
                    break;
                }
            }
            print(a);
        }
    }

    private static void print(int[] a){
        for (int num: a) {
            System.out.print(num+" ");
        }
        System.out.println();
    }

}
